
public class BinarySearch extends ArrayIndexOutOfBoundsException{

	public boolean search(int[] arr, int key, int low, int high){
		if(arr == null || low > high){
			return false;
		}
		if(arr.length == 1 && arr[0] == key){
			return true;
		}
		
		int mid = (high+low)/2;
		
		if(arr[mid] == key){
			return true;
		}
		else if(arr[mid]< key){
			return search(arr, key, mid+1, high);			
		}
		else {
			return search(arr, key, low, mid-1);
		}
		
		
		
	}
	
	public int searchForShift(int[] arr, int key, int left, int right){
		int mid = (left + right)/2;
		
		if(arr[mid] == key){
			return mid;
		}
		
		if(left > right){
			return -1;
		}
		
		//left is ordered normally
		if(arr[left] < arr[mid]){
			if(arr[left] <= key && arr[mid] >= key ){
				return searchForShift(arr, key, left, mid - 1);
			}
			else{
				return searchForShift(arr, key, mid + 1, right);
			}
		}
		
		//right is ordered normally
		else if(arr[right] > arr[mid]){
			if(arr[right] >= key && arr[mid] <= key){
				return searchForShift(arr, key, mid + 1, right);
			}
			else{
				return searchForShift(arr, key, left, mid - 1);
			}
		}
		
		//
		return -1;
	}
	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
		int[] arr1 = {4, 5, 6, 7, 8, 9, 10, 1, 2, 3};
		BinarySearch search = new BinarySearch();
		System.out.print(search.search(arr, 0, 0, 9));
		System.out.print(search.searchForShift(arr1, 11, 0, 9));
		

	}

}
